package com.bascker.algorithm.practice.greed;

import java.util.Objects;

/**
 * 去除重复字母:
 *   给你一个字符串 s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 * @author bascker
 * @apiNote from leetcode T316
 * @implNote https://gitee.com/bascker/algorithm/wikis/6%E3%80%81%E5%8E%BB%E9%99%A4%E9%87%8D%E5%A4%8D%E5%AD%97%E6%AF%8D?sort_id=3022983
 */
public class RmDuplicateLetter {

    /**
     * 贪心: 尽可能将最小字符放在前面
     */
    public String removeDuplicateLetters(String s) {
        if (Objects.isNull(s) || s.length() == 0) {
            return "";
        }

        // 统计重复的元素: 26 个小写英文字母
        final int[] arr = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            arr[c - 'a']++;
        }

        // pos: 跟踪当前字符串 s 中最小字符所在位置
        int pos = 0;
        for (int i = 0; i < s.length(); ++i) {
            // 最小位置
            if (s.charAt(i) < s.charAt(pos)) {
                pos = i;
            }

            // 确保其他字符至少出现 1 次
            if (--arr[s.charAt(i) - 'a'] == 0) {
                break;
            }
        }

        // 递归: replaceAll 部分是用于去重，确保子串中没有了当前 pos 位置字符
        return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll(String.valueOf(s.charAt(pos)), ""));
    }

}
